package Demo57;

/**
 * k个一组翻转链表
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/
 *
 * 解题思路, 先统计有多少个节点, 然后根据k, 计算出需要翻转多少组
 * 使用双循环, 外循环循环 n 次(多少组需要循环) , 内循环循环k次(翻转链表), 内循环使用头插法, 翻转链表
 * 期间需要注意保存下一组的位置, 和下一组存放的位置
 */

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode ret = new ListNode(0);
        ListNode cur = head;
        // 统计有多少个节点
        int n = 0;
        while(cur != null) {
            n++;
            cur = cur.next;
        }
        n /= k; // 判断需要翻转多少组

        ListNode prve = ret;
        cur = head;
        // 翻转 n 组
        while(n > 0) {
            // 记录下一组翻转节点存放的位置
            ListNode tmp = cur;
            int num = k;
            // 头插翻转链表
            while(num > 0) {
                ListNode next = cur.next;
                cur.next = prve.next;
                prve.next = cur;
                cur = next;
                num--;
            }
            // 更新下一组翻转节点存放的位置
            prve = tmp;
            n--;
        }
        // 处理边界, 剩下不需要翻转的
        prve.next = cur;
        return ret.next;
    }
}